SCCPC2026 A 那一年的秘密基地题解

发表于 2026-06-22 分类于题解

题目要求动态维护一个访问顺序。每次交换相邻两个点后，要在整棵树中重新选择根，使得“后访问的点是先访问点的祖先”的点对数量尽量少。

如果固定一个根去计算答案，根一变，所有祖先关系都会变，似乎很难维护。更好处理的方向是反过来：固定一对点，去看它会对哪些根产生贡献。

对两个点 $x,y$，记 $\operatorname{Side}(x,y)$ 为删去 $x$ 到 $y$ 路径上的第一条边后，包含 $x$ 的那个连通块。若当前选 $r$ 为根，那么

$$
x \text{ 是 } y \text{ 的祖先}
\Longleftrightarrow
r\in \operatorname{Side}(x,y).
$$

这是因为当根在 $x$ 这一侧时，从根走到 $y$ 的路径一定经过 $x$；反过来，如果从根到 $y$ 的路径经过 $x$，根也必然在删去第一条边后 $x$ 所在的那一侧。

于是，排列中一个有序点对的贡献就不再是“对某个根加一”，而是“对某个连通块里的所有根加一”。这样就可以维护每个点作为根时的危险度，并支持对一块连通区域整体加减。

为了把这种连通块更新变成常规数据结构操作，先以 $1$ 为根跑 DFS，得到每个点的子树区间。对于 $\operatorname{Side}(x,y)$，如果 $x$ 不是 $y$ 的祖先，它就是 $x$ 的子树；如果 $x$ 是 $y$ 的祖先，设 $z$ 是从 $x$ 走向 $y$ 的下一个点，那么它就是全集去掉 $z$ 的子树。也就是说，每次连通块更新都能表示成 DFS 序上的一个区间，或者一个区间的补集。用线段树维护每个根的当前危险度，即可支持区间加和全局最小值查询。

再看一次相邻交换。设本次交换的是

$$
u=a_x,\qquad v=a_{x+1}.
$$

除了 $u,v$ 这一对以外，任意两点的相对顺序都没有变化，所以答案数组的变化也只来自这一对。交换前，$u$ 在 $v$ 前面，这一对贡献的是“$v$ 是否为 $u$ 的祖先”，也就是对 $\operatorname{Side}(v,u)$ 加一；交换后变成“$u$ 是否为 $v$ 的祖先”，也就是对 $\operatorname{Side}(u,v)$ 加一。因此操作时只要把前者减掉、后者加上：

$$
\operatorname{Side}(v,u) \text{ 加 } -1,\qquad
\operatorname{Side}(u,v) \text{ 加 } 1.
$$

每个 $\operatorname{Side}$ 都能拆成常数个区间更新，所以一次交换只需要 $O(\log n)$。

剩下的是初始状态怎么建出来。设 $\operatorname{pos}(v)$ 表示点 $v$ 在访问顺序中的位置。我们枚举后出现的点 $v$，统计它与所有更早出现的点会对哪些根产生贡献。

先假装无论根在哪里，$v$ 都会作为前面所有点的祖先，那么可以对所有根加上

$$
\operatorname{pos}(v)-1.
$$

这当然会多算。删去点 $v$ 后，树会分成若干连通块。若根落在某个连通块 $C$ 内，那么 $C$ 内那些更早出现的点，从根到它们的路径不会经过 $v$，因此它们不该贡献。于是需要在这个连通块上减去

$$
|{u\in C\mid \operatorname{pos}(u)<\operatorname{pos}(v)}|.
$$

这些连通块仍然可以表示成子树或子树补集，所以最终也还是线段树上的区间加。

上式中的计数可以离线完成。按 $\operatorname{pos}(v)$ 从小到大扫描，用树状数组在 DFS 序上标记已经出现过的点。这样查询任意子树里已经出现过多少点，就是一次区间求和。得到所有需要减去的数量后，把每个点 $v$ 对初始答案数组的贡献加入线段树即可。

建好初始线段树后，根的最小危险度就是线段树全局最小值；之后每次交换只做两次 $\operatorname{Side}$ 更新，再输出全局最小值。

预处理、离线统计和建初值的复杂度为 $O(n\log n)$，每次交换复杂度为 $O(\log n)$。总时间复杂度为

$$
O((n+q)\log n).
$$